// 从前序和中序构造二叉树
// 根据一棵树的中序遍历与后序遍历构造二叉树。
import Foundation

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}


class Solution {
    var inorder: [Int] = []
    var postorder: [Int] = []
    var step: Int = 0
    var map: [Int: Int] = [:]
    
    func build(_ left: Int, _ right: Int) -> TreeNode? {
        if left > right {
            return nil
        }
        if let curRootIdx = map[self.postorder[self.step]] {
            let node = TreeNode(self.inorder[curRootIdx])
            // 需要注意的是，与前序不同，后序是逆向扫描后序序列，且应当先递归右子树
            self.step -= 1
            node.right = build(curRootIdx + 1, right)
            node.left = build(left, curRootIdx - 1)
            return node
        }
        return nil
    }
    
    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        self.inorder = inorder
        self.postorder = postorder
        self.step = inorder.count - 1
        for (idx, value) in inorder.enumerated() {
            map[value] = idx
        }
        let root = build(0, inorder.count - 1)
        return root
    }
}


